package main.old.new_2023.last.month_6;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description:
 * //TODO 剑指 Offer35. 复杂链表的复制
     * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，
     * 还有一个 random 指针指向链表中的任意节点或者 null。
 *
 * //todo 剑指 Offer 18. 删除链表的节点
     * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
     * 返回删除后的链表的头节点。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0609 {

    //删除链表的节点
    public ListNode deleteNode(ListNode head, int val) {
        //双指针，如果要删除，直接指向被删除的下一个，就是链表的删除操作
        ListNode pre = head;
        ListNode cur = head.next;
        if (pre.val == val){
            return pre.next;
        }
        while (cur != null && cur.val != val){
            pre = cur;
            cur = cur.next;
        }
        if (cur != null){
            pre.next = cur.next;
        }
        return head;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    //复杂链表的复制
    Map<Node, Node> nodeMap = new HashMap<>();
    public Node copyRandomList(Node head) {
        //hash表 + 递归
        if (head == null){
            return null;
        }
        if (!nodeMap.containsKey(head)){
            Node node = new Node(head.val);
            node.next = copyRandomList(head.next);
            node.random = copyRandomList(head.random);
            nodeMap.put(head,node);
        }

        return nodeMap.get(head);
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static void main(String[] args) {
        Solution0609 solu = new Solution0609();
        ListNode a= new ListNode(4);
        ListNode b= new ListNode(5);
        ListNode c= new ListNode(1);
        ListNode d= new ListNode(9);
        ListNode e= new ListNode(7);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        ListNode listNode = solu.deleteNode(a, 5) ;
        System.out.println(listNode);


    }

}
